﻿//#define TRACE_1
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions.Problems
{
    /*
     * 

Consider the consecutive primes p1 = 19 and p2 = 23. It can be verified that 1219 is the smallest number such that the last digits are formed by p1 whilst also being divisible by p2.

In fact, with the exception of p1 = 3 and p2 = 5, for every pair of consecutive primes, p2 > p1, there exist values of n for which the last digits are formed by p1 and n is divisible by p2. Let S be the smallest of these values of n.

Find ∑ S for every pair of consecutive primes with 5 ≤ p1 ≤ 1000000.

     * */
    class Problem134 : IProblem
    {
        public string Calculate()
        {
            int limit = 1000000;
            long[] p = new long[limit];
            p[0] = 2;

            SieveOfAtkin sieve = new SieveOfAtkin(limit);
            for (int i = 1, j = 3; i < p.Length; i++)
            {
                while (!sieve.IsPrime(j))
                    j += 2;
                p[i] = j;
                j += 2;
                if (p[i] >= limit)
                    break;
            }

            Console.WriteLine("Start");

            int[] lookup = new int[]
            {
                1, 2, 3, 4, 5, 6, 7, 8, 9, //1
                0, 0, 0, 0, 0, 0, 0, 0, 0,
                7, 4, 1, 8, 5, 2, 9, 6, 3, //3
                0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0,
                0, 0, 0, 0, 0, 0, 0, 0, 0, 
                3, 6, 9, 2, 5, 8, 1, 4, 7, //7
                0, 0, 0, 0, 0, 0, 0, 0, 0,
                9, 8, 7, 6, 5, 4, 3, 2, 1  //9
            };

            long sum = 0;

            for (int i = 2; p[i] < limit; i++)
            {

                long p1 = p[i];
                long p2 = p[i + 1];

                long lastDigit = p2 % 10;
                long numofdigits = CommonFunctions.NumberOfDigits(p1);
                long modulo = (long)Math.Pow(10, numofdigits);
                long target = modulo - (p2 - p1);

                long multiplicant = 0;

                for (long k = 0; k < numofdigits; k++)
                {
                    long last = target % 10;


                    if (last == 0)
                    {
                        target /= 10;
                        continue;
                    }

                    long factor = lookup[(lastDigit - 1) * 9 + last - 1];
                    multiplicant += factor * (long)Math.Pow(10, k);

                    target -= (p2 * factor) % (long)Math.Pow(10, numofdigits - k);
                    if (target < 0)
                        target += (long)Math.Pow(10, numofdigits - k);
                    target /= 10;
                }

                long result = multiplicant * p2 + p2 - p1;

                long n = result + p1;

                sum += n;

#if TRACE_1
                Console.WriteLine("p1 = {0}, p2 = {1}, n = {2}, sum = {3}", p1, p2, n, sum);
                Console.ReadKey();
#endif

            }
            return sum.ToString();
        }


    }
}
